package demo1;

import java.util.TreeMap;
import java.util.Set;
import java.util.Map;


/**
 * @Author liangzai
 * @Description:
 */
public class Test {

    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int count = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] % (nums2[j] * k)==0) {
                    count++;
                }
            }
        }
        return count;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for (int i = 0; i < lists.length; i++) {
            ListNode pcur = lists[i];
            while (pcur != null) {
                if(!map.containsKey(pcur.val)){
                    map.put(pcur.val,1);
                }else{
                    int val = map.get(pcur.val);
                    map.put(pcur.val,val+1);
                }
                pcur = pcur.next;
            }
        }
        ListNode cur = new ListNode();
        ListNode head = cur.next;
        Set<Map.Entry<Integer,Integer>> entry =  map.entrySet();
        for(Map.Entry<Integer,Integer> x : entry){
            int key = x.getKey();
            int val = x.getValue();
            while (val != 0) {
                cur.next = new ListNode(key);
                val--;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        map.put(1,3);
        map.put(3,2);
        map.put(6,3);
        map.put(11,1);

        ListNode cur = new ListNode(-1);
        ListNode pcur = cur;
        Set<Map.Entry<Integer,Integer>> entry =  map.entrySet();
        for(Map.Entry<Integer,Integer> x : entry){
            int key = x.getKey();
            int val = x.getValue();
            while (val != 0) {
                ListNode newnode = new ListNode(key);
                cur.next = newnode;
                val--;
                cur = cur.next;
            }
        }
    }

    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }



}
